#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

void swap(int* p1, int* p2)
{
	int x = *p1;
	*p1 = *p2;
	*p2 = x;
}

//除了child，其他的都是堆
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}

}

//左右子树都是大/小堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//选出左右子树中大的那一个
		if (child + 1 < n && a[child + 1] > a[child])   //防止无效数据的出现
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//排升序，建大堆  N*logN
void heapsort(int* a, int n)
{
	//建堆，逐个插入并向上调整  N*logN
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/

	//建堆，向下调整  N
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	//向下调整，排序调堆  N*logN
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{
	int a[] = { 2,3,9,8,7,5,6,0,1,4 };
	heapsort(a, 10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", *(a + i));
	}

	return 0;
}